package com.cg.leetcode;

import org.junit.Test;

/**
 * 450.删除二叉搜索树中的节点
 *
 * @program: LeetCode->LeetCode_450
 * @author: cg
 * @create: 2022-05-02 21:08
 **/
public class LeetCode_450 {

    @Test
    public void test450() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);

        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);
        System.out.println(deleteNode(root, 3));
    }

    /**
     * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
     * <p>
     * 一般来说，删除节点可分为两个步骤：
     * <p>
     * 首先找到需要删除的节点；
     * 如果找到了，删除它。
     * <p>
     * 示例 1:
     * <p>
     * 输入：root = [5,3,6,2,4,null,7], key = 3
     * 输出：[5,4,6,2,null,null,7]
     * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
     * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
     * 另一个正确答案是 [5,2,6,null,4,null,7]。
     * <p>
     * 示例 2:
     * 输入: root = [5,3,6,2,4,null,7], key = 0
     * 输出: [5,3,6,2,4,null,7]
     * 解释: 二叉树不包含值为 0 的节点
     * <p>
     * 示例 3:
     * 输入: root = [], key = 0
     * 输出: []
     * <p>
     * 提示:
     * 节点数的范围 [0, 10^4].
     * -10^5 <= Node.val <= 10^5
     * 节点值唯一
     * root 是合法的二叉搜索树
     * -10^5 <= key <= 10^5
     *
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        // 没找到删除的节点，遍历到空节点直接返回了
        if (root == null) {
            return null;
        }

        if (root.val > key) {
            // 去左子树删除
            root.left = deleteNode(root.left, key);
            // 去右子树删除
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            // 找到删除的节点
            // 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
            if (root.left == null) {
                return root.right;
            }
            // 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            if (root.right == null) {
                return root.left;
            }
            // 左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
            TreeNode temp = root.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            temp.left = root.left;
            root = root.right;
        }
        return root;
    }

}
